import java.util.HashSet;
import java.util.Set;

/**
 * 521. 去除重复元素
 * 给一个整数数组，去除重复的元素。
 * https://www.lintcode.com/problem/remove-duplicate-numbers-in-array/my-submissions
 *
 * 你应该做这些事
 * 1.在原数组上操作
 * 2.将去除重复之后的元素放在数组的开头
 * 3.返回去除重复元素之后的元素个数
 *
 * 样例
 * 例1:
 * 输入:
 * nums = [1,3,1,4,4,2]
 * 输出:
 * [1,3,4,2,?,?]
 * 4
 *
 * 解释:
 * 1. 将重复的整数移动到 nums 的尾部 => nums = [1,3,4,2,?,?].
 * 2. 返回 nums 中唯一整数的数量  => 4.
 * 事实上我们并不关心你把什么放在了 ? 处, 只关心没有重复整数的部分.
 *
 * 例2:
 * 输入:
 * nums = [1,2,3]
 * 输出:
 * [1,2,3]
 * 3
 * 挑战
 * 1.O(n)时间复杂度.
 * 2.O(nlogn)时间复杂度但没有额外空间
 *
 * 注意事项
 * 不需要保持原数组的顺序
 *
 * @author jeymingwu
 * @date 2019/10/8 15:31
 */
public class L0521_Remove_Duplicate_Numbers_In_Array {
    /**
     * @param nums: an array of integers
     * @return: the number of unique integers
     */
    public int deduplication(int[] nums) {
        // write your code here
        int sum = 0;
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; ++i) {
            if (!set.contains(nums[i])) {
                set.add(nums[i]);
                nums[sum] = nums[i];
                ++sum;
            }
        }
        return sum;
    }

    public static void main(String[] args) {
        int[] nums = {-3,8,-3,-5,-8,1,4,-5,-6,-10,2,10,9,10,5,-1,-6,5,1,-1,-4,9,0,9,-4,-5,-4,8,0,-3,6,8,5,-8,-7,-6,-6
                ,-1,6,-3,-7,2,-4,1,8,-1,6,0,-9,-8,-3,-10,0,-5,-2,10,-6,-4,-1,4,-3,-10,-8,3,7,4,10,-6,4,-1,7,-9,7,0,5,7,-5,-7,-6,-3};

        System.out.println(nums.length);
        L0521_Remove_Duplicate_Numbers_In_Array l0521 = new L0521_Remove_Duplicate_Numbers_In_Array();
        System.out.println(l0521.deduplication(nums));
        System.out.println(nums.toString());
    }
}
